package com.labuladong.datastructure;

import java.util.Arrays;
import java.util.NoSuchElementException;

//一个简单的动态数组代码实现
public class MyArrayList<E> {

    //真正存储数据的底层数组
    private E[] data;

    //当前数组中元素个数
    private int size;

    //数组初始容量
    private static final int INITIAL_CAPACITY = 1;

    //无参构造方法
    public MyArrayList() {
        this(INITIAL_CAPACITY);     // 调用带参构造方法
    }

    //带参构造方法
    public MyArrayList(int capacity) {
        // 检查容量是否为负数，如果是，则抛出异常
        if (capacity < 0) {
            // IllegalArgumentException 是 Java 标准库中的一个异常类，继承自 RuntimeException。
            // 它用于表示传递给方法或构造函数的参数无效或不合适。
            throw new IllegalArgumentException("Illegal Capacity: " + capacity);
        }

        // 创建一个泛型数组，用于存储元素
        // 由于 Java 不允许创建泛型数组，所以需要使用反射来创建泛型数组
        data = (E[]) new Object[capacity];
        size = 0;
    }

    //末尾添加元素
    public void addLast(E e) {
        // 如果当前数组容量已满，则扩容
        if (size == data.length) {
            reCapacity(2 * data.length);
        }

        data[size] = e;
        size++;
    }

    //指定位置插入元素
    public void add(int index, E e) {
        // 检查索引位置是否可以添加元素
        checkInsertIndexLegality(index);

        // 如果当前数组容量已满，则扩容
        if (size == data.length) {
            reCapacity(2 * data.length);
        }

        // 从最后一个元素开始，依次将元素后移，腾出位置
        // （注意应该从最后一个元素开始，防止覆盖）
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = e;
        size++;
    }

    //头部添加元素
    public void addFirst(E e) {
        add(0, e);
    }

    //删除末尾元素
    public E removeLast() {
        // 如果数组为空，则抛出异常
        if (isEmpty()) {
            // NoSuchElementException 是 Java 标准库中的一个异常类，继承自 RuntimeException。
            // 它用于表示在访问集合或迭代器中不存在的元素时发生的错误。
            throw new NoSuchElementException();
        }

        //缩容
        int capacity = data.length;
        if (size == capacity / 4) {
            reCapacity(capacity / 2);
        }

        E deleteData = data[size - 1];
        data[size - 1] = null;      // 必须置为 null，防止内存泄漏
        size--;

        return deleteData;
    }

    //指定位置删除元素
    public E remove(int index) {
        // 检查索引位置是否合法
        checkIndexLegality(index);

        //缩容
        int capacity = data.length;
        if (size == capacity / 4) {
            reCapacity(capacity / 2);
        }

        // 从 index 位置开始，依次将元素前移，覆盖 index 位置
        // （注意应该从 index 位置开始，防止覆盖）
        E deleteData = data[index];
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        data[size - 1] = null;
        size--;

        return deleteData;
    }

    //删除头部元素
    public E removeFirst() {
        return remove(0);
    }

    //查
    public E get(int index) {
        // 检查索引位置是否合法
        checkIndexLegality(index);

        return data[index];
    }

    //改
    public E set(int index, E e) {
        // 检查索引位置是否合法
        checkIndexLegality(index);

        E oldData = data[index];
        // 修改数组中指定位置的元素
        data[index] = e;

        return oldData;
    }

    //工具方法

    // 获取数组当前元素个数
    public int size() {
        return size;
    }

    //判断数组是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    //修改数组容量（扩容或缩容）
    private void reCapacity(int capacity) {
        E[] newData = (E[]) new Object[capacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    //检查索引位置是否可以存在元素（是否合法）
    private void checkIndexLegality(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index is illegal!" + ", Size: " + size);
        }
    }

    //检查索引位置是否可以添加元素（注意index = size时）
    private void checkInsertIndexLegality(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index is illegal!" + ", Size: " + size);
        }
    }

    //展示数组信息
    public void display() {
        System.out.println("size = " + size + " capacity = " + data.length);
        System.out.println(Arrays.toString(data));
    }

    public static void main(String[] args) {
        // 初始容量设置为 3
        MyArrayList<Integer> arr = new MyArrayList<>(3);

        // 添加 5 个元素
        for (int i = 1; i <= 5; i++) {
            arr.addLast(i);
        }   // 1 2 3 4 5

        arr.remove(3);              // 1 2 3 5
        arr.add(1, 9);           // 1 9 2 3 5
        arr.addFirst(100);              // 100 1 9 2 3 5
        int val = arr.removeLast();        // 100 1 9 2 3

        for (int i = 0; i < arr.size(); i++) {
            System.out.println(arr.get(i));
        }
    }

}
